779. K-th Symbol in Grammar - LeetCode Solution

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        def solve(n, k):
            
            if n==1 and k==1:
                return False
            
            mid = (2**(n-1))//2
            
            if k <= mid:
                return solve(n-1, k)
            else:
                return not solve(n-1, k-mid)
            
        
        if solve(N, K):
            return 1
        else:
            return 0